6. Zigzag Conversion Medium

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility)

完整介紹 https://leetcode.com/problems/zigzag-conversion/

題目是要把文字依 Z 的形狀排列後，再重新組起來
其實把文字在紙上寫一下，就會找出規則，並不太難，列為 Medium，其實有點偏 Easy
重點大概就是找出規則，如圖，

1 -> 7 需要經歷 6 步，同樣 7 -> 13 也是 6 步，最後一列也是一樣的規則
第二列 2 -> 6 需要 4 步，6 -> 8 需要 2 步，然後又是 4 步，2 步，4 步，2 步的變化
第三列 3 -> 5 需要 2 步，5 -> 9 需要 4 步，然後又是 2 步，4 步，2 步，4 步的變化

找到這個規則後就可以寫出程式了。

public class A0006_ZigzagConversion {
    
	public String convert(String input, int numRows) {
		if (numRows <= 1)
			return input;
		
		StringBuilder output = new StringBuilder();
		
		int step = (numRows - 1) * 2;
		
		for (int row=0; row<numRows; row++) {
		
			int step1 = step - row * 2; // if step is 8, row is 1, step1 6 step2 2
			int step2 = step - step1;
			int[] steps = new int[] {step1, step2};
			
			if (row == 0 || row == numRows-1)
				steps = new int[] {step, step};

			int idx = row;
			int stepIdx = 0;
			while (idx < input.length()) {
				output.append(input.charAt(idx));
				idx += steps[stepIdx%2];
				stepIdx++;
			}
		}
    	
    	return output.toString();
    }
}

這版先用 StringBuilder 較好懂，用 char[] 來存的話會更快一些，但其實也沒快到哪